package com.gitee.swsk33.algorithms.stack;

import java.util.Stack;

/**
 * 栈的应用常见算法
 */
public class StackUtils {

	/**
	 * 十进制转十六进制
	 *
	 * @param origin 原始待转换十进制数
	 * @return 十六进制数
	 */
	public static String decToHex(int origin) {
		// 先初始化一个栈
		Stack<Integer> stack = new Stack<>();
		while (origin != 0) {
			// 先把待转换数取余16得到的结果压入栈
			stack.push(origin % 16);
			// 然后自己除以16
			origin = origin / 16;
			// 自己除16之后若仍然不为零则重复上述步骤
		}
		// 运算完毕，把栈的内容弹出组装结果
		String result = "";
		while (!stack.empty()) {
			int eachInt = stack.pop();
			// 十六进制中10,11,12,13,14,15分别对应a,b,c,d,e,f，因此在此做个转换
			switch (eachInt) {
				case 10:
					result = result + "a";
					break;
				case 11:
					result = result + "b";
					break;
				case 12:
					result = result + "c";
					break;
				case 13:
					result = result + "d";
					break;
				case 14:
					result = result + "e";
					break;
				case 15:
					result = result + "f";
					break;
				default:
					result = result + eachInt;
					break;
			}
		}
		return result;
	}

	/**
	 * 判断表达式括号是否匹配
	 *
	 * @param expression 判断表达式
	 * @return 表达式括号是否匹配
	 */
	public static boolean isExpressionBracketsMatch(String expression) {
		// 实例化一个栈
		Stack<Character> stack = new Stack<>();
		// 遍历表达式字符
		char[] expChars = expression.toCharArray();
		for (char eachChar : expChars) {
			// 如果是左括号，就压入栈
			if (eachChar == '(' || eachChar == '[' || eachChar == '{') {
				stack.push(eachChar);
			} else if (eachChar == ')' || eachChar == ']' || eachChar == '}') {
				// 如果是右括号则将栈里的字符弹出一个
				// 如果遇到右括号，对栈弹出的时候，栈已经是空的了，说明有多余的右括号
				if (stack.empty()) {
					return false;
				}
				stack.pop();
			}
			// 别的字符不管
		}
		// 结束之后，如果栈为空说明表达式所有括号都有匹配
		return stack.empty();
	}

}